1. Field of the Invention
The present invention relates to the cyphering of digital data by means of algorithms intended to mask original data to make them undetectable by a possible pirate. The present invention more specifically relates to algorithms implementing a same transformation on different parts of the data to be coded.
2. Discussion of the Related Art
The cyphering/decyphering algorithms to which the present invention applies are generally executed by integrated circuits, either by means of state machines in wired logic, or by means of microprocessors executing a program in memory (generally a ROM). Such algorithms use secret keys specific to integrated circuits or to the user, which are exploited by the algorithm to code the data.
An example of a cyphering/decyphering algorithm to which the present invention most particularly applies is an algorithm known as the AES (Advanced Encryption Standard, FIPS PUB 197). This algorithm applies to a word or data code divided into blocks a same transformation several consecutive times based on different cyphering keys or, more specifically, on portions of a binary word forming a key.
FIG. 1 illustrates in a simplified flowchart the main steps of a conventional AES-type algorithm. Only the cyphering will be described, the decyphering using the inverse transformations.
This algorithm cyphers a word or code S0 of a predetermined number of bits (generally, 128 bits) into another word or code Sn of same size. The data to be cyphered are in fact formed of several words or codes resulting from a previous division of the data into words all having the same size. The cyphering and the decyphering are based on a secret key, the length of which (generally from 128 to 256 bits) conditions the cyphering security.
In practice, each step of an AES-type algorithm processes a matrix of four lines and four columns representing a word and each element of which is a byte or block of the processed 128-bit code. To simplify the following description, reference will be made for each step to a state considered as being a matrix.
To implement the cyphering or decyphering algorithm, 11 sub-keys each also comprised of 128 bits are first generated based on the secret key over 128 bits. More generally, based on a secret key of a number m of bits, n+1 sub-keys K0, . . . Ki, . . . Kn of m bits each are derived. These sub-keys are intended to be used by the algorithm as will be described hereafter in relation with FIG. 1.
The algorithm starts from an initial state (block 1, STATE INIT) S0 of the code or data word to be cyphered.
A first phase of the cyphering process is a so-called “bleaching” operation (block 2, ADDROUNDKEY) which consists of performing an XOR-type combination of initial state S0 with first sub-key K0. A first intermediary state S1 is obtained.
A second phase of the cyphering process consists of performing several turns or cycles of a same transformation T involving, at each turn, the state Si−1, obtained at the preceding turn and a current sub-key Ki. The number of turns of transformation T corresponds to n−1, that is, to the number of derived sub-keys, minus 2.
Each turn of transformation T is formed of four successively-applied operations. FIG. 2 illustrates in more detail these four operations on a matrix 20 of four lines and four columns of binary bytes to which an AES-type algorithm applies.
A first step (block 3, SHIFTROWS) consists of performing a rotation on the last three lines of matrix 20. First line 201 of matrix 20 is left unchanged. Second line 202 is rotated by one byte. Third line 203 is rotated by two bytes. Fourth line 204 is rotated by three bytes.
A second step (block 4, SUBBYTES) of a turn of transformation T is a non-linear transformation in which each byte of matrix 20′ forming the current state is replaced with its image taken from a substitution box (SBOX). As illustrated in FIG. 2, substitution box SBOX is obtained by two successive transformations. A first transformation (block 41, INV) consists of inverting the considered byte (the element of matrix 20′) in the finite body of order 28 (to correspond to the byte), byte 00 forming its own image. This inversion is followed by an affine transformation (block 42, AFFINE).
Examples of non-linear substitution transformations such as that disclosed hereabove are described, for example, in work “The Design of Rijndael” by Joan Daemen and Vincent Rijmen, published by Springer-Verlag (ISBN 3-540-42580-2) and in the AES standard (FIPS PUB 197), which references are incorporated herein by reference.
The third step (block 5, MIXCOLUMNS) of the turn of transformation T consists of considering each column of matrix 20″ resulting from the preceding step as a polynomial on the finite body of order 28, and of multiplying each of these polynomials by a combination polynomial P[X] modulo a polynomial M[X].
The last and fourth step of the turn of transformation T of rank i consists of applying sub-key Ki to matrix 20″ of the previous state to obtain a matrix 20′″, in which each element of matrix 20″ has been combined by XOR, bit to bit, with sub-key Ki (block 6, ADDROUNDKEY). Step 6 is the same as step 2 of the first cyphering phase, but performed with a different sub-key.
At the end of step 6, one obtains, for a turn of rank i, a state Si=T(Ki, Si−1). The four steps of the turn transformation are repeated n−1 times, that is, after step 6, it is returned to step 3 to perform a new turn with a next key.
The third phase of the cyphering algorithm (FIG. 1) consists, in a way, in a last turn, slightly modified as compared to that illustrated in FIG. 2. In fact, the steps of the turn transformation are reproduced except for the third one (MIXCOLUMNS). This amounts to successively performing steps 7, 8, and 9 corresponding to previously-described steps 3, 4, and 6 with, as the key for step 9, the last sub-key Kn.
State Sn=T′(Kn, Sn−1) is then obtained. This result is finally set up (block 10, RESULTFORM) for a subsequent use.
A known weakness of implementations on smart cards of AES-type algorithms or more generally of algorithms implementing several turns or cycles of a same transformation (T) on a code divided into blocks, is the sensitivity to attacks by analysis of the current consumption of the circuit executing the algorithm. Such an attack known as a DPA (Differential Power Analysis) consists of correlating the power consumption of the integrated circuit executing the algorithm with the secret keys used upon cyphering or decyphering. In practice, based on a message to be cyphered and on hypotheses about the secret key, a statistic correlation curve is established along time between the power consumption of the product for the message cyphering and an intermediary value calculated by the circuit. Such power consumption attacks are described in literature (see, for example, article “Differential Power Analysis” by Paul Kocher, Joshua Jaffe, and Benjamin Jun, published in 1999, CRYPTO Conference 99, pages 388-397, published by Springer-Verlag LNCS 1666), which is incorporated herein by reference.
A known solution to make the algorithms more resistant against differential power analysis attacks of the integrated circuit, consists of involving a random number in the execution of the algorithm. The use of a random value consists of masking the state at the beginning of the algorithm by this random value and of restoring the expected result at the end of the algorithm.
FIG. 3 partially and very schematically illustrates a first known technique of introduction of a random number Rd in the execution of an AES-type algorithm. Starting from an initial state of the matrix (block 11, STATEINIT), a bit-to-bit XOR type combination (block 12, +) with a random number Rd is performed. This number is thus introduced before step 2 of combination with first sub-key K0. This random number Rd must then be taken into account at some stages of the algorithm. First, in non-linear transformation steps 4 and 8 (SUBBYTES), a substitution box (SBOXRd) taking the random number into account must be used. Then, for each turn transformation, after the introduction of current key Ki (step 6), an XOR-type combination (block 13, +) with number Rd must be performed. Moreover, after step 13, the obtained result is combined (block 15, +) by XOR with an amount MC(SR(Rd)) corresponding to the application of the row shifting SR (SHIFTROWS) and column mixing MC (MIXCOLUMNS) functions to number Rd.
After the last transformation T′, the combination (block 16, +) by XOR of the obtained result with value SR(Rd) corresponding to the application of the row shifting to value Rd enables recovering the expected result.
The necessary use of a substitution box which is a function of the random number compels to recalculate this box for each cyphering or decyphering. This recalculation of the substitution boxes, necessary to obtain a good resistance against DPA attacks, results in a strong need for memory in the integrated circuit and lengthens the algorithm execution time by the necessary calculation time. For example, for codes (matrixes) over 128 bits, the recalculation of a substitution box SBOXRd for each byte of the state requires 16 boxes of 256 bytes, which amounts to 4 kilobytes of memory. Such a memory is far from being negligible when integrated, for example, in a smart card.
FIG. 4 illustrates a second conventional solution to involve a random value in a cyphering algorithm of AES type. This solution is described in article “An implementation of DES and AES, secure against some attacks” by M. L. Akkar and C. Giraud, published at the CHES conference 2001 (Springer-Verlag editors).
This solution consists of replacing the use of substitution boxes with transformations calculated at each turn of the algorithm. The result is the same, in that it leads to a substitution of the different matrix bytes. What changes is the way to obtain this substitution.
According to this solution, two random numbers Rd1 and Rd2 are used, and made to intervene at different steps of the algorithm. First random number Rd1 intervenes at the beginning (between blocks 1 and 2) and is added (XOR-type combination 22). Second random value Rd2 is introduced into the turns of the transformation, be it the n−1 identical transformations T or the last transformation T′.
The result of row shifting step 3 or 7 is combined by a polynomial multiplication 23 with coefficients on the finite body of order 28 (modulo an irreducible polynomial) with random value Rd2. Then, the obtained resulting matrix is added (XOR-type combination) with a matrix representing the result of the previous operation (Si*Rd2). This addition is symbolized by a block 25 in FIG. 4.
The two previous operations are performed before byte substitution step 24 which here is essentially comprised of two transformations. A first transformation (block 241, INV) consists of inverting each byte of the matrix resulting from step 25. Then, the product (byte by byte modulo an irreducible polynomial) of initial state Si by the inverse (Rd2−1) of the random value is added (XOR) to this inverse matrix (block 242, +). The result is then multiplied (block 243, X) by random value Rd2. There again, this is a polynomial multiplication. Finally, the last byte substitution step 24 of the matrix consists in an affine transformation 244 (AFFINE). At the end of step 24, the resulting matrix is submitted to the step of addition of the corresponding sub-key (step 6 or 9).
In a turn of a transformation, the step following step 24 is step 5 (MIXCOLUMNS). Then, after step 6, the obtained result is combined (block 26, +) by XOR with value Rd1. The result of addition 26 is combined (block 27), still by XOR, with result (MC(AF(SR(Rd1)))) of the polynomial column mixing processing (MC) of affine transformation AF applied to the row shifting SR applied to value Rd1.
In last transformation T′, the step following step 24 is step 9 with key Kn. Finally, the obtained result is combined (block 29, +) by XOR with the result (AF(SR(Rd1))) of affine transformation AF applied to row shifting SR applied to value Rd1. The output of block 29 provides the state to be set up by step 10.
Such a solution requires less memory than the first conventional solution illustrated in relation with FIG. 3. However, it considerably increases the algorithm execution time. Indeed, at each turn of the algorithm, the operation corresponding to the substitution becomes complex and requires many operations modulo a polynomial.
The problem of the processing by a random number is essentially due to the fact that, in an algorithm of the type to which the present invention applies, the substitution operation is a non-linear operation.